package com.mystudy.leetcode.problem.tree.p_530;

import com.mystudy.leetcode.base.TreeNode;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/7/24 20:42
 * @Description 二叉搜索树的最小绝对差
 */
public class Solution {

    int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        //一个节点的最小绝对差，必然在右子树的最小节点，与左子树的最大节点直接产生。
        if (root.left != null) {
            int leftMax = Math.abs(root.val - maxMum(root.left).val);
            min = leftMax > min ? min : leftMax;
             getMinimumDifference(root.left);
        }
        if (root.right != null) {
            int rightMin = Math.abs(root.val -miniMum(root.right).val);
            min = rightMin > min ? min : rightMin;
            getMinimumDifference(root.right);
        }
        return min;
    }

    private TreeNode miniMum(TreeNode node) {
        if (node.left == null) {
            return node;
        }
        return miniMum(node.left);
    }

    private TreeNode maxMum(TreeNode node) {
        if (node.right == null) {
            return node;
        }
        return maxMum(node.right);
    }


    TreeNode pre = null;
    public int getMinimumDifference2(TreeNode root) {
      //中序遍历，记录前一个值，计算差值
        inOrder(root);
        return min;
    }

    private void inOrder(TreeNode node){
        if(node == null){
            return;
        }
        inOrder(node.left);
        if(pre != null){
            int ans = Math.abs(pre.val - node.val);
            min = ans>min?min:ans;
        }
        pre = node;
        inOrder(node.right);
    }

}
